187. Repeated DNA Sequences

1. Question

The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.

For example, "ACGAATTCCG" is a DNA sequence. When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

2. Examples

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]

3. Constraints

• 1 <= s.length <= 10⁵
• s[i] is either 'A','C', 'G', or 'T'.

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/repeated-dna-sequences 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

将每个长度为10的子串遍历入map，value为出现的次数。将第二次出现的加入返回答案的列表中。

class Solution {
  public List<String> findRepeatedDnaSequences(String s) {
    List<String> ans = new ArrayList<>();
    int n = s.length();
    Map<String, Integer> map = new HashMap<>();
    for (int i = 0; i + 10 <= n; i++) {
      String cur = s.substring(i, i + 10);
      int cnt = map.getOrDefault(cur, 0);
      if (cnt == 1) ans.add(cur);
      map.put(cur, cnt + 1);
    }
    return ans;
  }
}